package 字符串.字符串匹配;

import java.util.Arrays;

/**
 * @Description:
 * @Author: Administrator
 * @Date: 2020-04-26
 */
public class KMP {
    //蛮力法
    static int BruteForceStringMatch(char T[], int n, char P[], int m) {
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && P[j] == T[i + j]) {
                j++;
            }
            if (j == m) {
                return i;
            }
        }
        return -1;

    }

    //构造前缀函数 abaabc
    public static int[] prefixTable(char P[], int m) {
        int F[] = new int[m];
        int i = 1, j = 0;
        while (i < m) {
            if (P[i] == P[j]) {
                F[i] = j + 1;
                i++;
                j++;
            } else if (j > 0) {
                j = F[j - 1];
            } else {
                i++;
            }
        }
        return F;
    }

    static int ListNode(char[] T, int n, char P[], int m, int[] F) {
        int i = 0, j = 0;
        int count = 0;
        while (i < n) {
            count++;
            if (T[i] == P[j]) {
                if (j == m - 1) {
                    System.out.println(count);
                    return i - j;
                }else{
                    i++;
                    j++;
                }
            } else if (j > 0) {
                j = F[j - 1];
            }else{
                i++;
            }
        }


        return -1;
    }

    public static void main(String[] args) {
        char[] s = "goodgoogle".toCharArray();
        char[] t = "google".toCharArray();
        char[] P = "google".toCharArray();
        System.out.println(BruteForceStringMatch(s, s.length, t, t.length));
        System.out.println(Arrays.toString(prefixTable(P, P.length)));
        System.out.println(ListNode(s, s.length, t, t.length,prefixTable(P, P.length)));

    }
}
